package com.fengye.algorithms.leecode;

/**
 * @Author fengye
 * @Date 2023/4/27 8:35
 **/
public class SurroundedRegions130 {

    public void solve(char[][] board) {
        int n = board.length;
        int m = board[0].length;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) {
                // 把边缘的找出来
                if((i==0||j==0||i==n-1||j==m-1)&&board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }

        for(int i=0;i<n;i++) {
            for (int j = 0; j < m; j++) {
                if(board[i][j] == 'O') {
                    board[i][j] = 'X';
                    // 边缘已经标记过的，改回去
                } else if(board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(char[][] board, int i, int j) {
        if(i < 0 || j < 0 || i>=board.length || j>=board[0].length || board[i][j] != 'O') {
            return;
        }

        board[i][j] = '#';
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j+1);
        dfs(board, i, j-1);
    }
}
